The following references are all hereby incorporated herein by reference in their entireties, and are referenced throughout the specification using the reference in brackets:    [3G212] 3G TS25.212 V3.1.1 (1999-12), http://www.3gpp.org    [Ber93] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding”: Turbo codes (1), “in Proc. ICC” 93, May 1993., Geneva, Switzerland, pp 1064-1070.    [Ber95] U.S. Pat. No. 5,446,747 entitled “Error-Correction Coding Method With at Least Two Systematic Convolutional Codings in Parallel, Corresponding Iterative Decoding Method, Decoding Module and Decoder,” issued on Aug. 29, 1995 in the name of Claude Berrou.    [Cho00] L. F. Choy, I. J. Fair, W. A. Krzymien, “Complexity-Performance Trade-offs in Turbo Codes for IMT-2000”, , in Proc. 2000 IEEE Vehicular Technology Conference, Boston, USA, pp 4.6.2.4    [Div95] D. Divsalar and F. Pollara, “Multiple Turbo Codes for Deep-Space Communications”, The JPL TDA Progress Report 42-121, January-March 1995, May 15, 1995.    [Div96A] S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “A Soft-Input Soft-Output APP Module for Iterative Decoding of Concatenated Codes”, IEEE Communications Letters, January, 1997    [Kha99] Khaleghi, F.; Khandani, A.; Secord, N.; Gutierrez, A. “On symbol-based turbo codes for cdma2000”. Wireless Communications and Networking Conference, 1999. WCNC. 1999 IEEE, 1999 Page(s): 471-475 vol.1    [MiC00] H. Michel, A. Worn, and Nobert Wehn, “Influence of Quantization on the Bit-Error Performance of Turbo-Decoders,”, In Proc. 2000 IEEE Vehicular Technology Conference, Tokyo, Japan, pp 581-585.    [Moh99] Mohamadreza Marandian Hagh, “Design of turbo coded modulations for bandwidth limited channels”, M.S. thesis, University of Tehran, March 1999.    [Moh02] Mohamadreza Marandian Hagh, Jose Fridman, Zoran Zvonar and Masoud Salehi, “Performance Analysis of Sliding Window Turbo Decoding Algorithms for 3GPP FDD Mode”, International Journal of Wireless Information Networks, IJWIN, January 2002, pages 39-54.    [Ric99] A. J. Richardson, “Performance of WCDMA Turbo Code Decoders—Part 1”, Imagicom Technical Report TR01-001. Sep. 20th, 1999.    [Rob95] Patrick Robertson, “Improving Decoder and Code Structure of Parallel Concatenated Recursive Systematic (Turbo) Codes”, 1994, Third Annual International Conference on Universal Personal Communications, San Diego, USA, pp 183-187.    [Woo99] Jason P. Woodard, “Implementation of High Rate Turbo Decoders for Third Generation Mobile Communications”, IEE Colloquium on Turbo Codes in Digital Broadcasting, 1999, pp 12.1-12.6.    [Wor00] Alexander Worm, Peter Hoeher, and Norbert Wehn, “Turbo-Decoding without SNR Estimation ”, IEEE Communication Letter, Vol. 4, No. 6, June 2000.
The turbo coding (TC) scheme [Ber95] has been considered for many advanced communication systems. For example, turbo coding has been specified as the channel coding technique for high date rate traffic channels in Third Generation Partnership Project (3GPP) wireless Code Division Multiple Access (CDMA) systems. The 3GPP TC scheme uses two Recursive Systematic Convolutional (RSC) codes in parallel with an interleaver in between them. FIG. 1 shows the structure of a standard 3GPP TC encoder.
In order to increase turbo code performance, encoder termination is applied on both RSC encoders individually. Trellis termination makes the encoder return to state zero after all data bits are transmitted. This allows beginning and ending states to be known at the receiver. Furthermore, both systematic and parity bits in each RSC encoder in the termination procedure are sent through the channel. This means that no puncturing applies on the systematic bits of the second RSC encoder at termination time. The coding rate of the turbo code in 3GPP standard is R=1/3 and, considering there are three bits of memory in each RSC encoder in the turbo code encoder, there are eight states per constituent encoder. The transfer function of each 8 state constituent encoder of turbo code is:
                              G          ⁡                      (            D            )                          =                  [                      1            ,                                          1                +                D                +                                  D                  3                                                            1                +                                  D                  2                                +                                  D                  3                                                              ]                                    (        1        )            
Taking the tail bits from the shift register feedback after all information bits are encoded performs trellis termination. Tail bits are added after the encoding of information bits.
The first three tail bits are used to terminate the first constituent encoder while the second constituent encoder is disabled. The last three tail bits are used to terminate the second constituent encoder while the first constituent encoder is disabled. Also, it is practical to use the termination information of the two RSC encoders in an iteration stopping algorithm in the receiver.
FIG. 2 shows a trellis diagram for each RSC constituent encoder. This trellis consists of eight states. The state labels correspond to input values of the encoder memory from left to right, for example, S3=(110) corresponds to input with equivalent polynomial 1+1×D+0×D2.
The interleaver length for the turbo code encoder is a function of the input data length. Since the input data length in 3GPP standard varies from 40 to 5114 bits discontinuously, the interleaver length must change in the same range. It is known that the performance of an iterative turbo code decoder strongly depends on the interleaver structures. From an implementation point of view, it is impractical to find a good interleaver pattern for each input data length and store the various interleaver patterns in the memory at the receiver. Typically, an algorithm that generates “almost good” interleaver patterns for every input data length is used. In 3GPP, a prime number sequence generator is used for this purpose. More details can be found in [3G212].
The turbo code decoder uses an iterative decoding technique. FIG. 3 shows a general block diagram of an iterative turbo code decoder. Iterative decoding is a low complexity sub-optimum decoding strategy that approaches the performance of an optimum maximum likelihood (ML) decoding algorithm in high signal to noise ratios. The optimum ML decoding for turbo codes requires a huge hyper-trellis with a large number of states that takes into account all memories in the two constituent encoders and the internal interleaver [Div96]. It is known that number of states in ML algorithms is an exponential function of total number of memories in the encoder. For example in 3GPP system, and for a received block with length N=100, optimal ML decoder requires a trellis with 2106 states!
Simulations of turbo decoders in the Third Generation Partnership Project (3GPP) applications have shown that the performance of the overall system is closely related to the performance of the decoder, particularly for small frame sizes. A typical turbo decoder is based on an iterative structure constructed from MAP (Maximum a posteriori) SISO (soft input soft output) decoders as basic building blocks. The MAP algorithm is one of the oldest SISO decoding algorithms for soft decoding of block codes. Since the introduction of turbo codes, many other SISO decoding algorithms have been introduced for serial, parallel, and hybrid concatenation detection systems [Div96].
The LogMAP algorithm is a log domain version of the MAP algorithm that is less complex than the MAP algorithm. The LogMAP algorithm (as well as the MAP algorithm) is not well-suited for implementation on any Digital Signal Processor (DSP), particularly because it requires many non-linear operations including exponential and logarithm operations.
The max-LogMAP algorithm is a low complexity version of the LogMAP algorithm. It uses an approximation and is appropriate for hardware and DSP implementation. Unfortunately, the max-LogMAP algorithm does not perform as well as the LogMAP algorithm. Simulations have shown a performance degradation of about 0.4-0.6 dB in turbo code decoders using the max-LogMAP algorithm as compared to the LogMAP algorithm.